package a00_LeetCode.Queue;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author quan
 * @Description 双队列实现栈
 * 请你仅使用两个队列实现一个后入先出（LIFO）的栈，支持普通栈的全部四种操作（push、top、pop 和 empty）。
 * @Date 2023/3/23 15:29
 */
public class Num225_MyStackByTwoQueue {
    /**
     * 思想：创建两个队列q1,q2，让新元素入q2,q1保存所有的元素
     * 如果q1为空，则直接交换两者的名字（也就是此时只有一个元素入队列）
     * 如果q1中不为空，则此时现将q1的所有元素弹出再入q2，再交换两者的名字。此时q1中的弹出顺序就与栈的顺序一致了。
     */
    //创建两个队列
    //q1用来存储所有的元素值，q2作为辅助
    Queue<Integer> q1 = new LinkedList<>();
    Queue<Integer> q2 = new LinkedList<>();
    //入队列
    public void push(int x) {
        //让所有的新元素入q2
        q2.offer(x);
        //判断q1是否有元素：有元素则要弹出并添加到q2
        while (!q1.isEmpty()){
            q2.offer(q1.poll());
        }
        //交换两者的名字
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }
    //弹出
    public int pop() {
        return q1.poll();
    }
    //查看队首元素
    public int top() {
        return q1.peek();
    }
    //判断队列是否为空
    public boolean empty() {
        return q1.isEmpty();
    }
}
